package leo.mystudy.demo;

import leo.mystudy.pojo.TreeNode;

import java.util.*;

/**
 * @author leo
 * @version 1.0.0
 * @description 二叉树的遍历
 * @create 2022/3/12 17:23
 */
public class BinaryTreeForeach {

    public void preForeach(TreeNode treeNode, int dep) {
        if (treeNode == null) {
            return;
        }
        System.out.println(treeNode.val + "," + dep);
        preForeach(treeNode.left, dep + 1);
        preForeach(treeNode.right, dep + 1);
    }

    public void midForeach(TreeNode treeNode) {
        if (treeNode == null) {
            return;
        }
        midForeach(treeNode.left);
        System.out.println(treeNode.val);
        midForeach(treeNode.right);
    }

    public void lastForeach(TreeNode treeNode) {
        if (treeNode == null) {
            return;
        }
        lastForeach(treeNode.left);
        lastForeach(treeNode.right);
        System.out.println(treeNode.val);
    }

    public static void main(String[] args) {
        TreeNode treeNode = buildTestTreeNode();
        BinaryTreeForeach binaryTreeForeach = new BinaryTreeForeach();
//        binaryTreeForeach.leftView(treeNode);
//        System.out.println("------");
//        binaryTreeForeach.maxView(treeNode);
        binaryTreeForeach.preForeachWithStack(treeNode);
    }

    /**
     * 构建一个测试用二叉树
     *
     * @return :
     * 7
     * /\
     * 2      3
     * 1     5   4
     */
    public static TreeNode buildTestTreeNode() {
        TreeNode treeNode = new TreeNode(7);
        treeNode.left = new TreeNode(2);
        treeNode.left.left = new TreeNode(1);
        treeNode.right = new TreeNode(3);
        treeNode.right.left = new TreeNode(5);
        treeNode.right.right = new TreeNode(4);
        return treeNode;
    }

    /**
     * 二叉树的左视图
     *
     * @param treeNode
     */
    public void leftView(TreeNode treeNode) {
        if (treeNode == null) {
            return;
        }
        Map<Integer, Integer> map = new HashMap<>();
        preForeachForLeftView(treeNode, 0, map);
        map.entrySet().stream().sorted((Map.Entry.comparingByKey())).forEach(t -> System.out.println(t.getValue()));
    }

    /**
     * 二叉树的每层最大值视图
     *
     * @param treeNode
     */
    public void maxView(TreeNode treeNode) {
        if (treeNode == null) {
            return;
        }
        Map<Integer, Integer> map = new HashMap<>();
        preForeachForMaxValue(treeNode, 0, map);
        map.entrySet().stream().sorted((Map.Entry.comparingByKey())).forEach(t -> System.out.println(t.getValue()));
    }

    public void preForeachForLeftView(TreeNode treeNode, int dep, Map<Integer, Integer> map) {
        if (treeNode == null) {
            return;
        }
        map.put(dep, treeNode.val);
        preForeachForLeftView(treeNode.right, dep + 1, map);
        preForeachForLeftView(treeNode.left, dep + 1, map);
    }

    public void preForeachForMaxValue(TreeNode treeNode, int dep, Map<Integer, Integer> map) {
        if (treeNode == null) {
            return;
        }
        map.compute(dep, (k, o) -> {
            if (o == null) {
                return treeNode.val;
            } else {
                return Math.max(treeNode.val, o);
            }
        });
        preForeachForLeftView(treeNode.left, dep + 1, map);
        preForeachForLeftView(treeNode.right, dep + 1, map);
    }

    public void preForeachWithStack(TreeNode treeNode) {
        Stack<TreeNode> stack = new Stack<>();
        stack.push(treeNode);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            System.out.println(node.val);
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
    }

    public void midForeachWithStack(TreeNode treeNode) {
        Stack<TreeNode> stack = new Stack<>();
        stack.push(treeNode);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            System.out.println(node.val);
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
    }

    /**
     * 层序遍历
     *
     * @param treeNode
     */
    public void floorForeach(TreeNode treeNode) {
        LinkedList<TreeNode> list = new LinkedList<>();
        list.add(treeNode);
        while (!list.isEmpty()) {
            TreeNode node = list.pop();
            System.out.println(node.val);
            if (node.left != null) {
                list.addLast(node.left);
            }
            if (node.right != null) {
                list.addLast(node.right);
            }
        }
    }


}
